package test;
/*
题目：198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
数据
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 */
public class leetcode198_dajiajieshe {
    //动态规划题目   每个房间要么偷，要么不偷
    //递归方式  复杂度为t(n)=t(n-1)+t(n-2)  为指数级别,过不了测试  该方法是从前往后偷
    public static int rob(int a[], int begin) {
        if (a.length == 0)
            return 0;
        if (begin == a.length - 1) return a[begin];   //到达最后还没偷，或者偷了倒数第三个，需要加上最后一个,如果偷了倒数第二个，那么就会+2，begin==a.length
        if (begin == a.length - 2) return Math.max(a[begin], a[begin + 1]);  //如果还剩最后两家没有偷并且前面一直没有偷，选择一个最大的偷
        int cur = a[begin] + rob(a, begin + 2);    //选择偷取这一家
        int butou = rob(a, begin + 1);     //这一家不偷
        return Math.max(cur, butou);
    }
    //非递归方式实现，减少计算重复项 使用数组进行缓存，这次使用从后往前偷  复杂度为o(n)
    public static int rob1(int a[]) {
        if (a.length == 0)
            return 0;
        if(a.length==1) return a[0];   //只有一个点，直接返回
        int [] cache=new int[a.length];//cache[i]表示从i向前面偷的最大金额
        cache[0]=a[0];    //从第一个向前面偷，只能偷第一个
        cache[1]=Math.max(a[0],a[1]);
        for(int i=2;i<a.length;i++){
            cache[i]=Math.max(a[i]+cache[i-2],cache[i-1]);
        }
        return cache[a.length-1];
    }
    public static void main(String[] args) {
        int a[]={2,7,9,3,1};
       // System.out.println(rob(a,0));
        System.out.println(rob1(a));
    }
}
